import java.util.Arrays;

/**
 * Created by dell_2 on 2016/8/4.
 */
public class Anagram {

    public int count;
    public int size;
    public int[] arr;

    public static void main(String[] args) {
        Anagram anagram = new Anagram();
        anagram.arr = new int[]{1,2,3,4,5,6,7,8,9,10,11,12};
        anagram.test();
        anagram.arr = new int[]{1,2,3,4,5,6,7,8,9,10,11,12};
        anagram.count = 0;
        anagram.test2();
//        anagram.arr = new int[]{1,2,3,4,5,6,7,8,9,10,11,12};
//        anagram.test3();

    }

    private void test2() {
        long l = System.currentTimeMillis();
        quanpailie(0);
        System.out.println(System.currentTimeMillis() - l);
    }
    private void test3() {
        long l = System.currentTimeMillis();
        do {
            //System.out.println(++count+","+Arrays.toString(arr));
        }while (nextPermutation());
        System.out.println(System.currentTimeMillis() - l);
    }

    private boolean nextPermutation() {
        for (int i = arr.length-1; i >=1; i--) {
           if(arr[i-1]<arr[i]){
               int k = i - 1;
               int j = getMinBigIndex(k);
               swap(k,j);
               roate(k+1,arr.length-1);
               return true;
           }
        }
        return false;
    }

    private int getMinBigIndex(int k){

        for (int i = arr.length-1; i >=0; i--) {
           if(arr[i]>arr[k]){
               return i;
           }
        }
        System.out.println("返回-1"+"k:"+k+"-->"+Arrays.toString(arr));
        return -1;
    }

    public void roate(int s,int e){
        int len = (e-s)/2;
        for (int i = 0; i <=len; i++) {
            swap(s+i,e-i);
        }
    }





    public void quanpailie(int n) {
        if(n==arr.length-1) {
            //System.out.println(++count+","+Arrays.toString(arr));
        }

        for (int i = n; i < arr.length; i++) {
            swap(n, i);
            quanpailie(n + 1);
            swap(n, i);
        }
    }

    public void swap(int i, int j) {
        if(i==j)return;
        int tem = arr[i];
        arr[i] = arr[j];
        arr[j] = tem;
        //System.out.println("count"+(count+=3));
    }


    public void test() {
        long l = System.currentTimeMillis();

        size = arr.length;
        doAnagram(size);
        System.out.println(System.currentTimeMillis() - l);
    }


    public void doAnagram(int newSize) {
        if (newSize == 1) {
            //displayWord();
            return;
        }
        for (int i = 0; i < newSize; i++) {
            doAnagram(newSize - 1);
            rotate(newSize);
            //displayWord();
        }
       // displayWord();
    }

    public void rotate(int newsize) {
        //System.out.println("滚动:"+newsize);
        int j;
        int position = newsize -1;
        int temp = arr[position];
        for (j = position; j > 0; j--) {
            arr[j]=  arr[j - 1];
          //  System.out.println("count"+(++count));
        }
        arr[0] = temp;
    }

    public void displayWord() {
        System.out.println(++count + "\t" + Arrays.toString(arr));

    }
}
